--------------------- Little Spline Guide --------------------- Written by Jani "Flame / Pygmy Projects" Vaarala Amiga ftpadministrator of x2ftp.oulu.fi Formulas from December 1986 BYTE article "FREE-FORM CURVES ON YOUR MICRO" by Steve Enns (starting from page 225) Spreading Freely spread. But! Making money out of this is not allowed! New versions (if needed) will be at FTP-site x2ftp.oulu.fi Corrections 25.1.1995 --- in example t=0 --> 1.0 .. 2.3.1995 --- some errors in matrix forms corrected. My intention is NOT to give ANY mathematical background of splines, but just to give the formulas and give some ideas for fast and easy (haha 8) spline use. FORMULAS -------- Bezier Form ----------- Developed by Pierre Bézier. 1° Matrix form / P1 \ C(t) = [t³ t² t 1] B | P2 | | P3 | \ P4 / where B is / -1 3 -3 1 \ B = | 3 -6 3 0 | | -3 3 0 0 | \ 1 0 0 0 / P1, P2, P3 and P4 are spline control points (points which guide the curve) (see example 1). And t is "spline-scale" which varies from 0.0 to 1.0. When t is 0.0, the curve is on point P1. As t approaches 1.0 the curve approaches point P4 (passing points P2 and P3). When t reaches 1.0 the curve is on point P4. 2° Equation form C(t) = ( -t³ + 3*t² - 3*t + 1) * P1 + ( 3*t³ - 6*t² + 3*t ) * P2 + (-3*t³ + 3*t² ) * P3 + ( t³ ) * P4 Note that C(t) gives only one coordinate. If you want to use 2D-splines then you must first calculate C(t) with P1-P4 values being x-coordinates, and then calculate C(t) with P1-P4 values being y-coordinates. For 3D-splines you must calculate C(t) three times etc. Example 1: (2D-bezier) ---------- Control points (x-spline point, y-spline point) (100,100) (150,50) (200,150) (250,100) should give sine-like curve (see SINE) starting from coordinate (100,100) and ending at (250,100). B-Spline form ------------- Matrix form / P(i-1) \ C(t) = [t³ t² t 1] B | P(i) | | P(i+1) | \ P(i+2) / where B is / -1 3 -3 1 \ B = | 3 -6 3 0 | | -3 0 3 0 | \ 1 4 1 0 / 2° Equation form C(t) = (-1/6*t³ + 1/2*t² - 1/2*t + 1/6) * P(i-1) + ( 1/2*t³ - t² + 2/3) * P(i) + (-1/2*t³ + 1/2*t² + 1/2*t + 1/6) * P(i+1) + ( 1/6*t³ ) * P(i+2) where P(i) is "current point" (point around the curve is being calculated. If N is the amount of control points, then i goes from 2 to n-2, and for every i t varies from 0.0 to 1.0. B-Spline curve begins from P(2) but P(1) (point before) has effect on the curve. As you can see from the formula, only four points affect our curve around one control point. As you see this B-Spline form allows user to have as many control points as desired. Bézier curves can also be utilized this way, but because B-Spline follows control points more closely I have chosen the B-Spline in my productions. Basic spline(draw) loop should be like: n = amount of spline controlpoints s = step (how many values / control point) for ( i = 2 --> n-2 ) for ( t=0.0 --> 1.0 step s) x = C(t) With x-control points y = C(t) With y-control points .... setpoint(x,y, ....) CONNECTING SPLINE(S) -------------------- To make the spline connected (end goes to beginning) you should copy the first 3 control points ( P(0), P(1) and P(2) ) to end of the control points. (This was a feature in my spline editor, thanks to Silver Eagle for the idea) If you want to connect 2 or more splines together then you should make the first 3 points in 2nd spline the same as in 1st spline etc etc ... USAGE ----- As you can see there are 4 t³-operations, 3 t²-operations and 4 multiplications with control points. That gives total of 4*2 + 3 + 4 = 15 multiplications. That makes 30 for one 2D-point which is too much for practical use. Coders with some experience should see that [t³ t² t 1] * B (the coefficients of control points) can be pretabled to reduce the amount of multiplications to only 4 / control point. So for 2D-point this would be 8 multiplications (not so bad). In Extension (1st in Assembly'93 amiga demo competition) the movements (in Shapecity and Dotcity) were done using my spline-routine, which had 1024 byte table for coefficients (that is 256 coeffs/control point). My "Morpher" routine used splines to create smooth morph. The morphing is done very easily. I made a spline-editor and we calculated some nice looking (filled) spline-figures. To make it morph I made linear (mistake!) slide from one spline control point set to another. Because of the lack of time I didn't have time to make the the morph use non-linear (S-curve) slide (that is why the morph isn't that smooth as it could be). SINE (maybe some other curves too ?) ------------------------------------ My littlebrother (Sami "Silver Eagle / Pygmy Projects" Vaarala) has used succesfully splines to create approximation of sine. In G-Force (Assembly'94 amiga 40k introcompo winner) Sami used 11 spline controlpoints to make the sine (45 degrees of it) and some values for scaling the sine. In G-Force the sine calculation code was around 20 instructions and data for the sine was around 15 16-bit words. And it calculated 40k of sinetable in around 20 frames (2/5 second) which had 16-bit sine values (32767 -> -32768) and had average error on sine values less than 1! (For example, If the real value would be 4123 then the value (from approximation) would be 4122 or 4124.) (All this work was done, because he needed large sinetables and math-libraries couldn't be used (competition rules)) If you have any suggestions/flames: (snail mail) Jani Vaarala Tellervontie 2 A 15 90570 Oulu Finland (email) flame@stekt.oulu.fi (questions/suggestions about this text or something. Please dont fill my mailbox with zillion questions about usual coding stuff (because you can ask your questions in comp.amiga.programmer) ftpadm@x2ftp.oulu.fi (questions about the programming site x2ftp.oulu.fi) Special thank to Harri Kinnunen for pointing me out the article (BYTE'86).